"""
问题：编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

解题思路：
根据二维矩阵的排序规律，从矩阵的右上角开始搜索矩阵元素matrix[i][j]：

如果target > matrix[i][j]，i++往下移动一行；
如果target < matrix[i][j]，j--往左移动一行；
否则，找到target。
设二维矩阵的行数为m，列数为n

时间复杂度：O(m + n)
空间复杂度：O(1)

"""

from typing import List


class Solution:
    def search_matrix(self, matrix:List[List[int]], target: int):
        if len(matrix) <= 0:
            return False
        row = len(matrix)
        colum = len(matrix[0])
        i,j = 0, colum-1
        while i < row and j>=0:
            if target < matrix[i][j]:
                j -= 1
            elif target > matrix[i][j]:
                i += 1
            else:
                return True
        return False


if __name__ == '__main__':
    s = Solution()
    matrix = [[1,   4,  7, 11, 15],
            [2,   5,  8, 12, 19],
            [3,   6,  9, 16, 22],
            [10, 13, 14, 17, 24],
            [18, 21, 23, 26, 30]]

    print(s.search_matrix(matrix, 18))